In the related art, as a device which calculates a traveling plan of a vehicle, a device which stratifies a traveling plan into an upper level plan and a lower level plan, and calculates the upper level plan and the lower level plan is known (see Patent Literature 1). In the device described in Patent Literature 1, the upper level plan is calculated in accordance with the traveling policy of the vehicle, and the lower level plan is calculated in accordance with changes in the ambient environment. Accordingly, in the device described in Patent Literature 1, traveling plan calculation which flexibly copes with changes in the ambient environment while satisfying the traveling policy of the vehicle is realized.